Search Algorithms: Object-Oriented

Implementation (Part A)

• Conventional vs. AI Algorithms

• Local Search Algorithms

• Genetic Algorithm

• Implementing Hill-Climbing Algorithms

• Defining ‘Problem’ Class

• Adding Gradient Descent

• Defining ‘HillClimbing’ Class

– There are many optimization problems that require a lot of time to

solve but no efficient algorithms have been identified

– Exponential algorithms are useless except for very small

problems

Example: Traveling Salesperson Problem:

The salesperson wants to minimize the total traveling cost required

to visit all the cities in a territory, and return to the starting point

® Efficiency is the issue!

• Nearest neighbor heuristic: always goes to the nearest city

– Given a starting city, there are (n – 1) + (n – 2) + ··· + 1 = n(n – 1)/2

cases to consider

solution

• AI algorithms use heuristics or randomized strategies to find a near

optimal solution quickly

– State space = set of “complete” configurations

(e.g., complete tours in TSP)

– Find optimal configuration according to the objective function

– Find configuration satisfying constraints (e.g., n-queens Problem)

– Current configuration:

– Candidate neighborhood configurations:

– Move a queen to reduce number of conflicts

– Almost always solves n-queens problems almost instantaneously

for very large n, e.g., n = 1 million

– Location: state

– Elevation: heuristic cost function or objective function

– Continually moves in the direction of increasing value

– Also called gradient ascent/descent search

Hill-Climbing Search

– Efficiency of valley-descending + completeness of random walk

– Escape local minima by allowing some “bad” moves

But gradually decrease their step size and frequency

• Analogy with annealing:

Boltzman distribution p(x) =

e

–E(x)/kT

– T decreased slowly enough ® always reach the best state

– Devised by Metropolis et al., 1953, for physical process modeling

– Widely used in VLSI layout, airline scheduling, etc.

• If the move improves the situation, it is always accepted

• Otherwise, the move is accepted with probability e

–

–

E : the amount by which the evaluation is worsened

○ The acceptance probability decreases exponentially with the

– T : temperature, determined by the annealing schedule

○ They become less likely as T decreases

• If the annealing schedule lowers T slowly enough, a global optimum

will be found with probability approaching 1

• The initial temperature is often heuristically set to a value so that the

probability of accepting bad moves is 0.5

– Each individual (state) is represented as a string over a finite

alphabet (called chromosome)—most commonly, a string of 0s

and 1s

• Each individual is rated by the fitness function

– Crossover frequently takes large steps in the state space early in

the search process when the population is quite diverse, and

smaller steps later on when most individuals are quite similar

• Each locus is subject to random mutation with a small independent

probability

• Advantage of GA comes from crossover:

– Is able to combine large blocks of letters that have evolved

independently to perform useful functions

1. Randomly select 2 individuals with replacement

2. Select the one with the best fitness as the winner

(ties are broken randomly)

• Uniform crossover:

– If the probability of head p = 0.5, the average number of crossover

points is l/2, where l is the length of the chromosome

called crossover rate

– Crossover rate close to 1 is popular

• Bit-flip mutation for binary representation:

– Each bit is flipped with a small mutation probability called